package com.dyz.leetcode._11_comprehensiveApplication;

import com.dyz.leetcode.TreeNode;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class _653_findTarget {
    //二叉查找树 中叙遍历是有序数列O(n)
    public boolean findTarget(TreeNode root, int k) {
        if(root==null){return false;}
        List<Integer> nums = new ArrayList<>();

        inOrder(root, nums);

        int left= 0;
        int right = nums.size()-1;
        while (left<right){
            int sum = nums.get(left)+nums.get(right);
            if(sum==k){
                return true;
            }else if(sum<k){
                left++;
            }else{
                right--;
            }
        }
        return false;
    }

    private void inOrder(TreeNode root, List<Integer> nums) {
        if(root==null){return;}
        inOrder(root.left, nums);
        nums.add(root.val);
        inOrder(root.right, nums);

    }


    //使用hash查找
    //二叉查找树 中叙遍历是有序数列O(n)
    public boolean findTarget1(TreeNode root, int k) {
        if(root==null){return false;}

        HashSet<Integer> hashSet = new HashSet<>();
        return find(root, k, hashSet);

    }
    private boolean find(TreeNode node, int target, Set<Integer> set){
        if(node==null){return false;}
        if(set.contains(target-node.val)){return true;}
        set.add(node.val);
        return find(node.left, target, set) || find(node.right, target, set);

    }
}
